1. Field of the Invention
The present invention relates to a process of reassembling interleaved data packets in an ATM Architecture and reassembly control hardware therefor.
2. Description of the Related Art
Asynchronous Transfer Mode (ATM) is a communication architecture in which information is transported in small, fixed-length units or cells of 53 bytes. Frames or packets of information, which may be as long as 128 KB, are split into multiple cell units for transport. The transmission facilities of an ATM network are shared between many users such that cells belonging to many users are interleaved. The exchange of a message or “connection” between two nodes of the ATM network is identified by an address pair known as the Virtual Path Identifier (VPI) and Virtual Channel Identifier (VCI).
Test systems that analyze ATM networks, i.e., network analyzers, may be required to analyze up to 4096 (4 K) or more simultaneous connections and must be able to capture and display reassembled frames to perform the required analysis. The frames captured by the network analyzer are stored in a capture buffer in ascending timestamp order; the timestamp for a frame is the timestamp for the last byte of the last cell of the frame. The network analyzer may additionally be required to capture and display the cells in link order, as for example to allow examination of cell loss on poor networks. Furthermore, the network analyzer may also be required to perform frame payload filtering in which each frame received from the link is compared against a template or filter criteria and discarded if it fails to match the template. This frame payload filtering ensures that the capture buffer of the network analyzer contains only useful data i.e., data that is required for the analysis. In the frame payload filter, the template or filter criterion is compared with the frame header (which is encapsulated in the first few cells of the frame). The start of each frame must accordingly be delayed until the cells containing the frame header are received. However, unless the buffer is partitioned on a connection basis, it is difficult to introduce the necessary delay because the cells are physically scattered among other cells when they arrive.
The network analyzer may perform a statistical analysis which uses protocol information, frame length, and any errors in the re-assembled frame to collect Remote Monitoring (RMON) statistics. This statistical information is contained in the first few cells and the last cell of each frame. The network analyzer may also perform an expert analysis process that examines real time data to diagnose problems. The information used by the expert analysis process is contained in the same cells of the frame as the RMON statistics information.
The real time, and hence performance constrained, requirements of an ATM network analyzer are frame filtering, RMON, and expert analysis. Data must be stored in the capture buffer of the network analyzer at full line-rate, but is only required to be viewed post-capture. Since the viewing process is only required after capture of the information, it is less performance critical.
In the ATM realm, the Segmentation And Reassembly layer (SAR) for segmenting and reassembling frame cells is part of the ATM Adaptation Layer (AAL), which is the uppermost layer in the ATM architecture. This AAL provides the interface between ATM user network software and the ATM network itself The SAR layer of a source endpoint of the ATM network segments frames into the 48-byte payload field of cells (a 53-byte cell including a 5-byte header and the 48-byte payload) and the SAR layer of a destination endpoint of the ATM network receives the cells and reconstructs frames by reassembling the individual cell payloads. The Network Interlace Controller (NIC) cards of the source and destination end points, i.e., computers, connected to the network implement the frame reassembly function using a variety of methods.
In prior art reassembly processes, a number of bottlenecks prevent the host computer from receiving the captured data at the maximum rate that the network can support. One of these bottlenecks is the Direct Memory Access (DMA) process between the NIC card and the computer. This connection is typically made over a Peripheral Component Interconnect (PCI) bus which has an upper bandwidth limit of 133 Mbps (but typically lower in practice). The link rate supported by network analyzers is 622 Mbps at an Optical Carrier 12 (OC12) link and 2488 Mbps at an Optical Carrier 48 (OC48) link. The network is intended to be shared between many endpoints. Therefore, this difference between the bandwidth of the PCI bus at one endpoint and the network is not a problem. Ideally, the reassembly process is not the bottleneck for an endpoint, but the reassembly process typically reassembles frames for only one endpoint, and thus is not expected to reassemble all frames for all connections on a link simultaneously, i.e., at the full-line rate. Accordingly, the endpoint will discard frames if the incoming data exceeds its processing capacity.
In contrast to a typical endpoint, a network analyzer must be capable of capturing and filtering thousands of simultaneous connections at full line-rate. For example, 4K or more simultaneous frames may be multiplexed randomly onto a typical OC12 link. For the network analyzer to work properly, the reassembly process must not constitute a bottleneck in this capture and filtering process. That is, frames may be dropped because they do not meet a filter criterion, but not because the reassembly process is overloaded. The reliability of a network analyzer to capture the data or interest without regard to the loading of the network is paramount. RMON and expert analysis may use a sampled data approach which is more forgiving in that it does not require every frame; but the reassembly process must be fast enough to avoid development of a bottleneck under such circumstances.
In one prior art method for reassembling individual cells in frames, one cell at a time is accepted at a NIC card and passed on to a memory of the host system. The NIC card in these systems maintains a table of pointers to the frame buffers in system memory. Each cell is directed to an appropriate area of memory in accordance with the VPI/VCI of the cell for reassembly of the packet. This method is not, however, appropriate for a Network Analyzer which must provide packet reassembly at the line-rate.
A second prior art method, disclosed by U.S. Pat. No. 5,303,302, uses a temporary storage in a NIC card and reassembles frames in local memory, at least in part, before sending them to the host system memory. Since the lengths of the frames are variable and not known until the entire frame has been received, this method teaches that the buffer may be allocated in blocks with each block is large enough to hold a number of reassembled cells and pointers for backward and forward linking of other blocks within that connection. The control logic for this arrangement controls free buffer space, buffer overflow, maintenance of the linked list pointers, and transfers to the host system memory of fully reassembled or partially reassembled frames.
In a third known method disclosed, for example, in U.S. Pat. No. 5,870,394 and U.S. Pat. No. 6,088,355, cells are stored in cell slots in a temporary buffer as they are received in unassembled order. In this method, separate linked lists are created for each connection as the cells are received and stored ii the buffer. Reassembly occurs just prior to transfer of the frame to the host memory using the linked list to sequentially retrieve all cells of the frame. In this method, the controlling logic must similarly control the free buffer space, buffer overflow, maintenance of the linked lists, and transfer to the host system memory of reassembled or portions of reassembled frames.
The first above-described prior art reassembly method is ineffective for full line-rate reassembly at the bit rates required for an ATM network analyzer. While the second and third above-described methods improve the performance of the reassembly over the first method, both require full reassembly of frames. Certain traffic flows will cause buffer overflows and prevent transfer to the host of some frames that should be transferred, thereby limiting system performance. Furthermore, there is no definitive size for the temporary buffers of these prior art methods that will prevent such an overflow, as the frames are variable in size. An attempt to limit an overflow requires a very large buffer to support frames of as long as 128 KB for the 4K or more connections that may be interleaved. To cope with a worst case traffic scenario in which frames for each one of the 4K or more open connections are interleaved, a minimum of 512 MB (4K connections*128 KB per connection) is required. The temporary storage can only be zeroed or emptied when a reassembly of a packet or frame has completed. Depending on the outgoinig bandwidth from the reassembly process and the buffer format used, the time required to empty the buffer may necessitate the availability of additional storage.
The requirement of the second above-described prior art reassembly method that the frames be reassembled in a temporary storage can be excessively wasteful of storage for short frames. Furthermore, the link lists required by this method may requires a large amount of data and processing time.
In the third above-described prior art method, the size of the link lists used to reassemble the data of each connection increases as the buffer increases in size. Since the linked lists are needed on a per connection basis and because of the random nature of the traffic pattern, each link list must index each cell in the buffer. As a result of this substantial memory requirement the link list may need to be stored in an external RAM rather than the memory of the controlling Application Specific Integrated Circuit (ASIC), thereby reducing performance. Furthermore, multiple accesses are required to maintain and access each list during each cell period, introducing performance problems at the OC12 link rates.